package com.ruoyi.system.exper;

import io.swagger.models.auth.In;

import java.util.*;

public class ClientToCompany {

    //  找出值小的 （双指针）
    public int threeSumSmaller(int[] nums, int target) {

        int length = nums.length;
        int total = 0;
        for (int i = 0; i < length; i++) {
            int sum = target - nums[i];
            int left = i + 1;
            int right = length - 1;
            while (left < right) {
                int subsum = nums[left] + nums[right];
                if (subsum < sum) {
                    total += (right - left);
                    left++;
                } else { // 为啥要在else 里面减，，因为有可能第二个数也是加起来比较小得
                    right--;
                }


            }
        }
        return total;
    }


    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int a = A.length;
        int b = B.length;
        int n = a + b;
        int[][] ints = new int[n][2];
        int alength = 0;
        int blength = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < n; i++) {
            int aleft = A[alength][0];
            int aright = A[alength][1];
            int bleft = B[blength][0];
            int bright = B[blength][1];
            if (aleft < bleft) {
                left = bleft;
            } else {
                left = aleft;
            }
            alength++;
            blength++;
            if (aright < bright) {
                right = bright;
            } else {
                right = aright;
            }

            int[] ints1 = new int[2];
            ints1[0] = left;
            ints1[1] = right;
            ints[i] = ints1;
        }
        return null;
    }


    public int[] intervalIntersection(int[] a, int[] b) {
        int n = b.length + b.length;
        int[] ints = new int[n];
        int am = 0;
        int bm = 0;
        for (int i = 0; i < n; i++) {
            if (a[am] > b[bm]) {
                bm++;
                ints[i] = b[bm];
            } else {
                am++;
                ints[i] = a[am];

            }

        }

        return ints;
    }

    // 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

    public List<List<Integer>> zigzagLevelOrderQueue(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.add(root);
        Boolean left = true;
        ArrayList<List<Integer>> outList = new ArrayList<>(16);
        while (nodeQueue.size() > 0) {
            int size = nodeQueue.size();
            Deque<Integer> integers = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                // 栈中有数据
                TreeNode poll = nodeQueue.poll(); // 弹出来
                if (left) {
                    integers.addLast(poll.val);
                } else {
                    integers.addFirst(poll.val);
                }
                if (poll.left != null) {
                    nodeQueue.offer(poll.left);
                }
                if (poll.right != null) {
                    nodeQueue.offer(poll.right);
                }
            }
            left = !left;
            outList.add(new LinkedList<Integer>(integers));
        }
        return outList;
    }


    public List<List<Integer>> zigzagLevelOrderQueue1(TreeNode root) {
        ArrayList<List<Integer>> outList = new ArrayList<>();
        if (root == null) {
            return outList;
        }
        ArrayDeque<TreeNode> treeNodes = new ArrayDeque<>();
        treeNodes.add(root);
        int size = treeNodes.size();
        // 双端列表，既能往前增加，又能往后增加。
        Boolean left = true;
        while (size > 0) {
            LinkedList<Integer> integers = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = treeNodes.poll();
                if (left) {
                    integers.addLast(poll.val);
                } else {
                    integers.addFirst(poll.val);
                }
                if (poll.left != null) {
                    treeNodes.add(poll.left);
                }
                if (poll.right != null) {
                    treeNodes.add(poll.right);
                }
            }
            left = !left;
            outList.add(integers);
        }

        return outList;

    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 先左后右，
        ArrayList<List<Integer>> outList = new ArrayList<>(16);
        if (root == null) {

            return null;
        }
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(root.val);
        // 漏掉的就是你没思考到的。就是在增加你的理解，完善你的模型。
        outList.add(integers);
        circulate(root, outList, 2);

        return outList;
    }

    //[3,9,20,null,null,15,7]
    public void circulate(TreeNode treeNode, ArrayList<List<Integer>> outList, int mark) {
        if (treeNode == null) {
            return;
        }
        List<Integer> innerList = null;
        if (outList.size() < mark) {
            innerList = new ArrayList<>(16);
            outList.add(innerList);
        } else {
            innerList = outList.get(--mark);
        }
        // 此处循环是偶数
        if (mark / 2 == 0) {
            if (treeNode.right != null) {
                innerList.add(treeNode.right.val);
            }
            if (treeNode.left != null) {
                innerList.add(treeNode.left.val);
            }
            circulate(treeNode.left, outList, mark++);
            circulate(treeNode.right, outList, mark++);
        } else { // 奇数，，从左到右
            ArrayList<Integer> integers = new ArrayList<>();
            if (treeNode.right != null) {
                integers.add(treeNode.right.val);
            }
            if (treeNode.left != null) {
                integers.add(treeNode.left.val);
            }
            integers.addAll(innerList);
            innerList = integers;
            circulate(treeNode.right, outList, mark++);
            circulate(treeNode.left, outList, mark++);
        }


    }


}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    public List<List<Integer>> permute1(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        //  first =0    i =5   first = 1    一个一个固定，然后到最后就是所有就固定了。
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }


    public static void backtrack1(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 已经到最后
        if (first == n - 1) {
            // 全部已经选完了。
            res.add(new ArrayList<>(output)); // 因为output是一个暂时的存的，是会变得，所以要重新new 一个
        }
        for (int i = first; i < n; i++) {
            // 进行位置的调换
            Collections.swap(output, first, i); // 确定了一个
            // 循环去确定下一个
            backtrack1(n, output, res, first + 1);
            // 这一次转换的完了，需要变回来。进行下一个变化。。 这一步就是做的回溯操作。。因为上一个的结果已经算是解出来了。
            Collections.swap(output, i, first);
        }
    }


    public static List<List<Integer>> permute(int[] nums) {

        int length = nums.length;
        ArrayList<Integer> ins = new ArrayList<>();
        for (int num : nums) {
            ins.add(num);
        }
        ArrayList<List<Integer>> integers = new ArrayList<>();
        backtrack1(length, ins, integers, 0);

        return integers;
    }


    // 区间在这个里面的个数
    public int countRangeSum(int[] nums, int lower, int upper) {

        int length = nums.length;
        int[] sumRange = new int[length + 1];
        int sum = 0;
        // sumRange[0]=0;
        for (int i = 0; i < length; i++) {
            sum += nums[i];
            sumRange[i] = sum;
        }
        int n = 0;
        countTwoSum(n, sumRange, 0, length - 0, lower, upper);

        return 0;
    }

    private int countTwoSum(int ret, int[] sumRange, int left, int right, int lower, int upper) {

        if (right == left) {
            return 0;
        }
        int middle = (left + right) / 2;
        //  归并排序里面的拆分
        ret = countTwoSum(ret, sumRange, left, middle, lower, upper);
        ret = countTwoSum(ret, sumRange, middle + 1, right, lower, upper);

        // 拆分到合适的时机后
        int i = left;
        int l = middle + 1;
        int r = middle + 1;


        while (i < middle + 1) {
            while (l <= right && sumRange[l] - sumRange[i] <= lower) {
                l++;
            }
            while (r <= right && sumRange[r] - sumRange[i] <= upper) {
                r++;
            }
            ret += r - l;
            i++;
        }
        // 合并区间  两个排好序的数组进行合并
        // 临时数组
        int[] ints = new int[right - left + 1];
        int j = 0;
        int p = middle + 1;
        int p1 = left;
        // 通过临时数组，
        while (j < ints.length) {
            while (p1 > middle && j < ints.length) {
                //  左边已经遍历完成
                ints[j++] = sumRange[p++];
            }
            while (p > right && j < ints.length) {
                ints[j++] = sumRange[p++];
            }
            if (sumRange[p1] <= sumRange[p]) {
                ints[j++] = sumRange[p1++];
            } else {
                ints[j++] = sumRange[p++];
            }
        }
        //  数据同步， 从临时数组返回到真实数组

        for (int anInt : ints) {
            sumRange[left++] = anInt;
        }
        return ret;
    }


    class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            long s = 0;
            long[] sum = new long[nums.length + 1];
            for (int i = 0; i < nums.length; ++i) {
                s += nums[i];
                sum[i + 1] = s;
            }
            return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
        }

        public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {
            if (left == right) {
                return 0;
            } else {
                int mid = (left + right) / 2;
                int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
                int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
                int ret = n1 + n2;

                // 首先统计下标对的数量
                int i = left;
                int l = mid + 1;
                int r = mid + 1;
                while (i <= mid) {
                    while (l <= right && sum[l] - sum[i] < lower) {
                        l++;
                    }
                    while (r <= right && sum[r] - sum[i] <= upper) {
                        r++;
                    }
                    ret += r - l;
                    i++;
                }

                // 随后合并两个排序数组
                long[] sorted = new long[right - left + 1];
                int p1 = left, p2 = mid + 1;
                int p = 0;
                while (p1 <= mid || p2 <= right) {
                    if (p1 > mid) {
                        sorted[p++] = sum[p2++];
                    } else if (p2 > right) {
                        sorted[p++] = sum[p1++];
                    } else {
                        if (sum[p1] < sum[p2]) {
                            sorted[p++] = sum[p1++];
                        } else {
                            sorted[p++] = sum[p2++];
                        }
                    }
                }
                for (int j = 0; j < sorted.length; j++) {
                    sum[left + j] = sorted[j];
                }
                return ret;
            }
        }
    }

    //

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permute = permute(nums);
        System.out.println(permute);
    }
}